import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> ret;
    public List<Integer> path;
    boolean[] visited;
    public List<List<Integer>> permute(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        visited = new boolean[nums.length];
        dfs(nums);
        return ret;
    }

    private void dfs(int[] nums) {
        if(path.size() == nums.length) {
            //将路径添加进结果中
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            //当当前节点未使用时
            if(!visited[i]) {
                path.add(nums[i]);//添加当前节点到路径中
                visited[i] = true;//标记当前节点已经使用
                dfs(nums);
                //回溯
                visited[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = -prices[0]-fee;
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]-fee);
            dp[i][1] = Math.max(dp[i-1][0]+prices[i], dp[i-1][1]);
        }
        return dp[n-1][1];
    }
}